class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        int target = n * n;
        vector<bool> visited(target + 1, false);
        queue<pair<int, int>> q;
        
        q.push({1, 0});
        visited[1] = true;
        
        while (!q.empty()) {
            auto [curr, steps] = q.front();
            q.pop();
            for (int i = 1; i <= 6; ++i) {
                int next_num = curr + i;
                if (next_num > target) break;
                auto [r, c] = getCoordinate(next_num, n);
                if (board[r][c] != -1) {
                    next_num = board[r][c];
                }
                if (next_num == target) {
                    return steps + 1;
                }
                if (!visited[next_num]) {
                    visited[next_num] = true;
                    q.push({next_num, steps + 1});
                }
            }
        }
        return -1;
    }
    
private:
    pair<int, int> getCoordinate(int num, int n) {
        int row = (num - 1) / n;
        int col = (num - 1) % n;
        
        if (row % 2 == 1) {
            col = n - 1 - col;
        }
        
        row = n - 1 - row;
        
        return {row, col};
    }
};
